home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / MCASM.RAR / MC_ASM.EXE / WROX_ASM / CH10 / PROGRAMS / ARHH6.ASM < prev    next >
Assembly Source File  |  1994-05-30  |  12KB  |  667 lines
  1. ; Haffman coding
  2. ; Written by Malakhov K.A.
  3. ; Compile with TASM 3.0 or latter
  4. ;         TASM ARHH6.ASM /MX /ZX /O
  5. ; CALL:    haff_encode(char *buffinput,unsigned int inputlength,
  6. ;            char *buffoutput,unsigned int outputlength);
  7.  
  8. model large
  9.  
  10. PUBLIC    _haff_encode
  11.  
  12. .code
  13.  
  14. ; Haffman compression
  15. _haff_encode    PROC    C FAR
  16.         ARG    buffi:dword,ileng:word,buffo:dword,oleng:word
  17.         USES    ds,es,di,si,bx,cx,dx
  18.  
  19.         cld
  20.         mov    ax,oleng
  21.         mov    cs:counto,ax
  22.  
  23. @@implode_1:
  24. ; Procedure of bilding the tree
  25.         call    rdtree
  26.         cmp    ax,0
  27.         je    @@implode_n
  28. ; Provedure of coding
  29.         call    arhhaff
  30. @@implode_n:    ret
  31.  
  32. rdtree        proc    NEAR
  33. ; Initialize
  34.         mov    ax,ileng
  35.         mov    cs:counti,ax
  36.         mov    cs:CRCod,0
  37. ; Fill the table of characters
  38.         mov    cx,256
  39.         xor    al,al
  40.         push    cs
  41.         pop    es
  42.         lea    di,chartab
  43. @@impl_015:    stosb
  44.         inc    al
  45.         loop    @@impl_015
  46. ; clear hafftab & freqtab
  47.         mov    cx,1024
  48.         xor    al,al
  49.         lea    di,hafftab
  50.     rep    stosb
  51.         mov    cx,256
  52.         lea    di,freqtab
  53.         xor    ax,ax
  54.     rep    stosw
  55.         mov    cs:codcnt,0
  56. ; Calculate the number of repeat bytes in file
  57.         lea    di,freqtab
  58.         mov    ax,word ptr buffi+2
  59.         mov    ds,ax
  60.         mov    si,word ptr buffi
  61.         mov    cx,cs:counti
  62. @@impl_020:    lodsb
  63.         add    cs:CRCod,al
  64.         xor    ah,ah
  65.         shl    ax,1
  66.         mov    bx,ax
  67.         add    bx,di
  68.         inc    word ptr es:[bx]
  69.         loop    @@impl_020
  70. ; Sort
  71.         mov    cx,256
  72.         xor    di,di
  73.         xor    dl,dl
  74. @@impl_030:    push    cx
  75.         dec    cx
  76.         mov    si,di
  77.         add    si,2
  78.         mov    dh,dl
  79.         inc    dh
  80. @@impl_040:    push    cx
  81.         mov    ax,word ptr cs:freqtab[di]
  82.         cmp    ax,0
  83.         jne    @@impl_050
  84.         mov    ax,word ptr cs:freqtab[si]
  85.         cmp    ax,0
  86.         je    @@impl_060
  87.  
  88.         mov    bx,word ptr cs:freqtab[di]
  89.         mov    word ptr cs:freqtab[si],bx
  90.         mov    word ptr cs:freqtab[di],ax
  91.         mov    bl,dh
  92.         xor    bh,bh
  93.         mov    al,byte ptr cs:chartab[bx]
  94.         mov    bl,dl
  95.         mov    ah,byte ptr cs:chartab[bx]
  96.         mov    bl,dh
  97.         mov    byte ptr cs:chartab[bx],ah
  98.         mov    bl,dl
  99.         mov    byte ptr cs:chartab[bx],al
  100.  
  101. @@impl_050:    mov    ax,word ptr cs:freqtab[di]
  102.         mov    bx,word ptr cs:freqtab[si]
  103.         cmp    bx,0
  104.         je    @@impl_060
  105.         cmp    ax,bx
  106.         jbe    @@impl_060
  107.  
  108.         mov    word ptr cs:freqtab[si],ax
  109.         mov    word ptr cs:freqtab[di],bx
  110.         mov    bl,dh
  111.         xor    bh,bh
  112.         mov    al,byte ptr cs:chartab[bx]
  113.         mov    bl,dl
  114.         mov    ah,byte ptr cs:chartab[bx]
  115.         mov    bl,dh
  116.         mov    byte ptr cs:chartab[bx],ah
  117.         mov    bl,dl
  118.         mov    byte ptr cs:chartab[bx],al
  119.  
  120. @@impl_060:    add    si,2
  121.         inc    dh
  122.         pop    cx
  123.         dec    cx
  124.         jz    @@impl_070
  125.         jmp    @@impl_040
  126. @@impl_070:    add    di,2
  127.         inc    dl
  128.         pop    cx
  129.         dec    cx
  130.         cmp    cx,1
  131.         jbe    @@impl_080
  132.         jmp    @@impl_030
  133. @@impl_080:
  134. ; Calculating the number of different symbols
  135.         mov    cx,256
  136.         push    cs
  137.         pop    ds
  138.         lea    si,freqtab
  139.         mov    cs:hafflen,0
  140. @@impl_085:    lodsw
  141.         cmp    ax,0
  142.         je    @@impl_088
  143.         inc    word ptr cs:hafflen
  144.         loop    @@impl_085
  145. @@impl_088:
  146. ; Init
  147.         mov    ax,word ptr buffo+2
  148.         mov    es,ax
  149.         mov    di,word ptr buffo
  150. ; Store CRC
  151.         mov    al,cs:CRCod
  152.         stosb
  153.         dec    word ptr cs:counto
  154. ; Store the length of header
  155.         mov    ax,cs:hafflen
  156.         dec    ax
  157.         stosb
  158.         dec    word ptr cs:counto
  159. ; Store header
  160.         mov    cx,cs:hafflen
  161.         xor    si,si
  162. @@impl_0880:    mov    al,cs:chartab[si]
  163.         stosb
  164.         dec    word ptr cs:counto
  165.         inc    si
  166.         loop    @@impl_0880
  167.  
  168.         mov    cx,cs:hafflen
  169.         xor    si,si
  170. @@impl_0881:    mov    ax,cs:freqtab[si]
  171.         stosw
  172.         dec    word ptr cs:counto
  173.         dec    word ptr cs:counto
  174.         add    si,2
  175.         loop    @@impl_0881
  176.  
  177.         mov    cs:savedi,di
  178. ; Building the tree
  179. ; Prepare the table of weights
  180.         mov    cx,256
  181.         push    cs
  182.         pop    es
  183.         lea    di,codtab
  184.         xor    al,al
  185.     rep    stosb
  186. ; MIN
  187. @@impl_089:    mov    bx,65535
  188.         xor    si,si
  189.         mov    cx,cs:hafflen
  190. @@impl_090:    mov    ax,cs:freqtab[si]
  191.         cmp    ax,0
  192.         je    @@impl_092
  193.         cmp    bx,ax
  194.         jbe    @@impl_092
  195.         mov    bx,ax
  196.         mov    cs:minpos1,si
  197. @@impl_092:    add    si,2
  198.         loop    @@impl_090
  199.  
  200.         mov    cs:exit,1
  201.         mov    bx,65535
  202.         xor    si,si
  203.         mov    cx,cs:hafflen
  204.         cmp    cx,1
  205.         ja    @@impl_094
  206.         mov    ax,cs:minpos1
  207.         shr    ax,1
  208.         mov    cl,1
  209.         call    shift
  210.         jmp    @@impl_220
  211. @@impl_094:    mov    ax,cs:freqtab[si]
  212.         cmp    ax,0
  213.         je    @@impl_096
  214.         cmp    bx,ax
  215.         jb    @@impl_096
  216.         cmp    si,cs:minpos1
  217.         je    @@impl_096
  218.         mov    bx,ax
  219.         mov    cs:exit,0
  220.         mov    cs:minpos2,si
  221. @@impl_096:    add    si,2
  222.         loop    @@impl_094
  223.  
  224.         mov    al,cs:exit
  225.         cmp    al,0
  226.         je    @@impl_098
  227.         jmp    @@impl_220
  228. @@impl_098:
  229.         mov    ax,cs:minpos1
  230.         shr    ax,1
  231.         mov    si,ax
  232.         mov    ax,cs:minpos2
  233.         shr    ax,1
  234.         mov    di,ax
  235.         mov    al,cs:codtab[si]
  236.         mov    ah,cs:codtab[di]
  237.         cmp    al,0
  238.         jne    @@impl_100
  239.         cmp    ah,0
  240.         je    @@impl_099
  241.         jmp    @@impl_125
  242. ; Variant 1
  243. @@impl_099:    inc    byte ptr cs:codcnt
  244.         mov    ax,si
  245.         mov    cl,0
  246.         call    shift
  247.         mov    ax,di
  248.         mov    cl,1
  249.         call    shift
  250.         mov    al,cs:codcnt
  251.         mov    cs:codtab[si],al
  252.         mov    cs:codtab[di],al
  253.         mov    si,cs:minpos1
  254.         mov    di,cs:minpos2
  255.         mov    ax,cs:freqtab[di]
  256.         add    cs:freqtab[si],ax
  257.         mov    cs:freqtab[di],0
  258.         jmp    @@impl_089
  259. ; Variant 2
  260. @@impl_100:
  261.         cmp    ah,0
  262.         je    @@impl_102
  263.         jmp    @@impl_140
  264. @@impl_102:
  265.         mov    ax,cs:minpos1
  266.         shr    ax,1
  267.         mov    si,ax
  268.         mov    dl,cs:codtab[si]
  269.         mov    cx,256
  270.         xor    si,si
  271. @@impl_105:    cmp    dl,cs:codtab[si]
  272.         jne    @@impl_110
  273.         push    cx
  274.         mov    ax,si
  275.         xor    cl,cl
  276.         call    shift
  277.         pop    cx
  278. @@impl_110:    inc    si
  279.         loop    @@impl_105
  280.  
  281.         mov    ax,cs:minpos2
  282.         shr    ax,1
  283.         mov    cl,1
  284.         call    shift
  285.  
  286.         mov    ax,cs:minpos1
  287.         shr    ax,1
  288.         mov    si,ax
  289.         mov    ax,cs:minpos2
  290.         shr    ax,1
  291.         mov    di,ax
  292.         mov    al,cs:codtab[si]
  293.         mov    cs:codtab[di],al
  294.  
  295.         mov    si,cs:minpos1
  296.         mov    di,cs:minpos2
  297.         mov    ax,cs:freqtab[di]
  298.         add    cs:freqtab[si],ax
  299.         mov    cs:freqtab[di],0
  300.         jmp    @@impl_089
  301. @@impl_125:
  302.         mov    ax,cs:minpos2
  303.         shr    ax,1
  304.         mov    si,ax
  305.         mov    dl,cs:codtab[si]
  306.         mov    cx,256
  307.         xor    si,si
  308. @@impl_130:    cmp    dl,cs:codtab[si]
  309.         jne    @@impl_135
  310.         push    cx
  311.         mov    ax,si
  312.         xor    cl,cl
  313.         call    shift
  314.         pop    cx
  315. @@impl_135:    inc    si
  316.         loop    @@impl_130
  317.  
  318.         mov    ax,cs:minpos1
  319.         shr    ax,1
  320.         mov    cl,1
  321.         call    shift
  322.  
  323.         mov    ax,cs:minpos2
  324.         shr    ax,1
  325.         mov    si,ax
  326.         mov    ax,cs:minpos1
  327.         shr    ax,1
  328.         mov    di,ax
  329.         mov    al,cs:codtab[si]
  330.         mov    cs:codtab[di],al
  331.  
  332.         mov    si,cs:minpos2
  333.         mov    di,cs:minpos1
  334.         mov    ax,cs:freqtab[di]
  335.         add    cs:freqtab[si],ax
  336.         mov    cs:freqtab[di],0
  337.         jmp    @@impl_089
  338. ; Variant 3
  339. @@impl_140:
  340.         mov    ax,cs:minpos1
  341.         shr    ax,1
  342.         mov    si,ax
  343.         mov    dl,cs:codtab[si]
  344.         mov    cx,256
  345.         xor    si,si
  346. @@impl_145:    cmp    dl,cs:codtab[si]
  347.         jne    @@impl_150
  348.         push    cx
  349.         mov    ax,si
  350.         xor    cl,cl
  351.         call    shift
  352.         pop    cx
  353. @@impl_150:    inc    si
  354.         loop    @@impl_145
  355.  
  356.         mov    ax,cs:minpos2
  357.         shr    ax,1
  358.         mov    si,ax
  359.         mov    dl,cs:codtab[si]
  360.         mov    cx,256
  361.         xor    si,si
  362. @@impl_155:    cmp    dl,cs:codtab[si]
  363.         jne    @@impl_160
  364.         push    cx
  365.         mov    ax,si
  366.         mov    cl,1
  367.         call    shift
  368.         pop    cx
  369. @@impl_160:    inc    si
  370.         loop    @@impl_155
  371.  
  372.         mov    ax,cs:minpos1
  373.         shr    ax,1
  374.         mov    si,ax
  375.         mov    dl,cs:codtab[si]
  376.         mov    ax,cs:minpos2
  377.         shr    ax,1
  378.         mov    si,ax
  379.         mov    dh,cs:codtab[si]
  380.         mov    cx,256
  381.         xor    si,si
  382. @@impl_165:    cmp    dl,cs:codtab[si]
  383.         jne    @@impl_170
  384.         mov    cs:codtab[si],dh
  385. @@impl_170:    inc    si
  386.         loop    @@impl_165
  387.  
  388.         mov    si,cs:minpos2
  389.         mov    di,cs:minpos1
  390.         mov    ax,cs:freqtab[di]
  391.         add    cs:freqtab[si],ax
  392.         mov    cs:freqtab[di],0
  393.         jmp    @@impl_089
  394. ; Calculating the number of bytes
  395. @@impl_220:    mov    di,2
  396.         mov    cx,256
  397. @@impl_230:    mov    al,cs:hafftab[di]
  398.         xor    ah,ah
  399.         xor    dx,dx
  400.         mov    bx,8
  401.         div    bx
  402.         mov    cs:hafftab[di],8
  403.         cmp    dx,0
  404.         je    @@impl_240
  405.         mov    cs:hafftab[di],dl
  406.         inc    ax
  407. @@impl_240:    mov    cs:hafftab[di+1],al
  408.         add    di,4
  409.         loop    @@impl_230
  410. ; Calculating the length of archieve
  411.         mov    ax,word ptr buffo+2
  412.         mov    ds,ax
  413.         mov    si,word ptr buffo
  414.         mov    cx,cs:hafflen
  415.         add    si,cx
  416.         add    si,2
  417.         push    cs
  418.         pop    es
  419.         lea    di,freqtab
  420.     rep    movsw
  421.  
  422.         mov    cs:fulleng,0
  423.         mov    cs:fullenb,0
  424.         mov    cx,256
  425.         xor    bx,bx
  426. @@impl_2400:    push    cx
  427.         mov    dl,cs:hafftab[bx+3]
  428.         cmp    dl,0
  429.         ja    @@impl_2401
  430.         jmp    @@impl_2406
  431. @@impl_2401:    dec    dl
  432.         xor    dh,dh
  433.  
  434.         mov    ax,bx
  435.         mov    cl,2
  436.         shr    ax,cl
  437.         mov    cx,256
  438.         xor    si,si
  439. @@impl_2402:    mov    ah,cs:chartab[si]
  440.         cmp    ah,al
  441.         je    @@impl_2403
  442.         inc    si
  443.         loop    @@impl_2402
  444.  
  445. @@impl_2403:    shl    si,1
  446.         mov    cx,cs:freqtab[si]
  447.         cmp    dx,0
  448.         je    @@impl_2404
  449.         mov    ax,dx
  450.         xor    dx,dx
  451.         mul    cx
  452.         add    cs:fulleng,ax
  453. @@impl_2404:    mov    al,cs:hafftab[bx+2]
  454.         xor    ah,ah
  455.         mul    cx
  456.         mov    cx,8
  457.         xor    dx,dx
  458.         div    cx
  459.         add    cs:fulleng,ax
  460.         add    dx,cs:fullenb
  461.         cmp    dx,8
  462.         jb    @@impl_2405
  463.         sub    dx,8
  464.         inc    word ptr cs:fulleng
  465. @@impl_2405:    mov    cs:fullenb,dx
  466. @@impl_2406:    add    bx,4
  467.         pop    cx
  468.         dec    cx
  469.         jz    @@impl_2407
  470.         jmp    @@impl_2400
  471. @@impl_2407:    mov    ax,cs:fullenb
  472.         cmp    ax,0
  473.         je    @@impl_2408
  474.         inc    word ptr cs:fulleng
  475. @@impl_2408:    mov    ax,cs:fulleng
  476.         mov    bx,cs:hafflen
  477.         shl    bx,1
  478.         add    bx,cs:hafflen
  479.         add    ax,bx
  480.         add    ax,2
  481.         cmp    ax,cs:counti
  482.         jae    @@impl_err
  483. @@impl_noerr:    mov    ax,1
  484.         jmp    @@impl_exi
  485. @@impl_err:    xor    ax,ax
  486. @@impl_exi:    ret
  487. rdtree        endp
  488.  
  489. ; Compression
  490. arhhaff        proc    NEAR
  491.  
  492.         mov    cs:shiftb,0
  493.         mov    ax,word ptr buffi+2
  494.         mov    ds,ax
  495.         mov    si,word ptr buffi
  496.         mov    ax,word ptr buffo+2
  497.         mov    es,ax
  498.         mov    di,word ptr cs:savedi
  499.  
  500. @@impl_250:    mov    ax,cs:counti
  501.         cmp    ax,0
  502.         ja    @@impl_270
  503.         mov    al,cs:shiftb
  504.         cmp    al,0
  505.         je    @@impl_255
  506.         dec    word ptr cs:counto
  507. @@impl_255:    jmp    @@impl_320
  508.  
  509. @@impl_260:    mov    cs:counti,ax
  510.         mov    si,word ptr buffi
  511. @@impl_270:    lodsb
  512.         dec    word ptr cs:counti
  513.         xor    ah,ah
  514.         mov    cl,2
  515.         shl    ax,cl
  516.         mov    bx,ax
  517.         mov    cs:currhaff,ax
  518.  
  519.         mov    ch,byte ptr cs:hafftab[bx+3]
  520.         cmp    ch,1
  521.         ja    @@impl_275
  522.         jmp    @@impl_300
  523. @@impl_275:    dec    ch
  524. @@impl_280:    mov    dl,byte ptr es:[di]
  525. ; Mask
  526.         mov    ax,0ff00h
  527.         mov    cl,byte ptr cs:shiftb
  528.         shr    ax,cl
  529.         and    dl,al
  530. ; Code
  531.         mov    ah,byte ptr cs:hafftab[bx]
  532.         xor    al,al
  533.         mov    cl,byte ptr cs:shiftb
  534.         shr    ax,cl
  535.         or    ah,dl
  536.         mov    byte ptr es:[di],ah
  537.         push    ax
  538.         inc    di
  539.         dec    word ptr cs:counto
  540.         mov    ax,cs:counto
  541.         cmp    ax,0
  542.         ja    @@impl_290
  543.  
  544.         jmp    @@implode_err
  545. @@impl_290:    pop    ax
  546.         mov    byte ptr es:[di],al
  547.         inc    bx
  548.         dec    ch
  549.         jz    @@impl_300
  550.         jmp    @@impl_280
  551. ; Last byte
  552. @@impl_300:    mov    dl,byte ptr es:[di]
  553. ; Mask
  554.         mov    ax,0ff00h
  555.         mov    cl,byte ptr cs:shiftb
  556.         shr    ax,cl
  557.         and    dl,al
  558. ; Code
  559.         mov    ah,byte ptr cs:hafftab[bx]
  560.         xor    al,al
  561.         mov    cl,byte ptr cs:shiftb
  562.         shr    ax,cl
  563.         or    ah,dl
  564.         mov    byte ptr es:[di],ah
  565.         mov    dx,ax
  566. ; Calculating the next shift
  567.         mov    bx,cs:currhaff
  568.         add    bx,2
  569.         mov    al,cs:shiftb
  570.         add    al,cs:hafftab[bx]
  571.         mov    cs:shiftb,al
  572.         cmp    al,8
  573.         jb    @@impl_315
  574.         sub    al,8
  575.         mov    cs:shiftb,al
  576.  
  577.         inc    di
  578.         dec    word ptr cs:counto
  579.         mov    ax,cs:counto
  580.         cmp    ax,0
  581.         ja    @@impl_310
  582.  
  583.         jmp    @@implode_err
  584. @@impl_310:    mov    ax,dx
  585.         mov    byte ptr es:[di],al
  586. @@impl_315:    jmp    @@impl_250
  587.  
  588. @@impl_320:    mov    ax,oleng
  589.         sub    ax,cs:counto
  590.         cmp    ax,0
  591.         ja    @@impl_330
  592.         inc    ax
  593. @@impl_330:    ret
  594.  
  595. @@implode_err:    xor    ax,ax
  596.         jmp    short @@impl_exit
  597. @@implode_noerr:
  598. @@impl_exit:    ret
  599. arhhaff        endp
  600.  
  601. ; Procedure of shifting bits
  602. shift        proc    NEAR
  603.         push    bx
  604.         push    di
  605.         push    dx
  606.         rcr    cl,1
  607.         pushf
  608.         mov    bx,ax
  609.         mov    al,cs:chartab[bx]
  610.         xor    ah,ah
  611.         mov    cl,2
  612.         shl    ax,cl
  613.         mov    di,ax
  614.         xor    bx,bx
  615.         mov    dx,bx
  616.         add    dx,1
  617. @@shift_010:    cmp    bx,dx
  618.         ja    @@shift_020
  619.         mov    al,cs:hafftab[di+bx]
  620.         popf
  621.         rcr    al,1
  622.         pushf
  623.         mov    cs:hafftab[di+bx],al
  624.         inc    bx
  625.         jmp    short @@shift_010
  626. @@shift_015:    mov    cs:errflag,1
  627.         jmp    short @@shift_030
  628. @@shift_020:    popf
  629.         mov    cl,byte ptr cs:hafftab[di+bx]
  630.         cmp    cl,16
  631.         ja    @@shift_015
  632. @@shift_030:    inc    byte ptr cs:hafftab[di+bx]
  633.         pop    dx
  634.         pop    di
  635.         pop    bx
  636.         ret
  637. shift        endp
  638.  
  639. ; DATA
  640. counti        dw    ?    ; Input bytes counter
  641. counto        dw    ?    ; Output bytes counter
  642. savedi        dw    ?
  643. hafflen        dw    ?
  644. errflag        db    ?
  645. shiftb        db    ?    ; Shift bytes
  646. currhaff    dw    ?
  647. minpos1        dw    ?
  648. minpos2        dw    ?
  649. codcnt        db    ?    ; Size of code
  650. exit        db    ?
  651. fulleng        dw    ?    ; Full length
  652. fullenb        dw    ?    ; Full length in bytes
  653. CRCod        db    ?
  654. ident        db    4dh,53h,49h
  655. freqtab        dw    257 dup(0)    ; Table of probability
  656. chartab        db    257 dup(?)    ; Table of characters
  657. codtab        db    256 dup(?)    ; Table of index
  658. hafftab        db    1024 dup(?)    ; Table of codes
  659.  
  660. @@imp_err:    xor    ax,ax
  661.         jmp    short @@imp_exit
  662. @@imp_noerr:
  663. @@imp_exit:    ret
  664. _haff_encode    ENDP
  665.  
  666.         END
  667.